package top.minuy.structure.tree.heap;

import top.minuy.util.generate.ArrayGenerator;
import java.util.Arrays;
/**
 * @author Minuy
 * @time 23:32
 * @date 2021/9/16
 */
public class Test {
    public static double testHeap(Integer[] arr, boolean isHeapify) {
        long startTime = System.nanoTime();
        MaxHeap<Integer> maxHeap;

        if (isHeapify) {
            // 使用Heapify
            maxHeap = new MaxHeap<>(arr);
        } else {
            maxHeap = new MaxHeap<>(arr.length);
            for (Integer i : arr) {
                maxHeap.add(i);
            }
        }

        boolean check = true;
        int lastOutE = maxHeap.extractMax();
        int OutE;
        for (int i = 1; i < arr.length; i++) {
            OutE = maxHeap.extractMax();
            if (lastOutE < OutE) {
                check = false;
            }
            lastOutE = OutE;
        }

        long endTime = System.nanoTime();

        System.out.println("time = " + (endTime - startTime) / 1000000000.0 + " s, check = " + check);

        return (endTime - startTime) / 1000000000D;
    }

    public static void main(String[] args) {
        int n = 1000000;
        Integer[] arr1 = ArrayGenerator.generateRandomArray(n, n);
        Integer[] arr2 = Arrays.copyOf(arr1,arr1.length);
        System.out.println("Without Heapify :");
        testHeap(arr1,false);
        System.out.println("With Heapify :");
        testHeap(arr2,true);
    }
}
